Основные определения

Везде, где не оговорено обратное, речь идёт про конечные графы. Существуют также бесконечные, не все определения для них сохраняются

Граф, подграф

Граф
Граф:

  • - мн-во вершин
  • - мн-во рёбер
    Графы бывают:
--- Ориентированный Неориентированный
Без кратных рёбер и петель
произвольное отношение. Вырожденные рёбра исключены (хотя это вопрос соглашения)
ребро <=> a -- начало ребра, b -- конец ребра

, то есть нет различия между и
Отношение симметрично, но симметричные пары не отличимы
нет (хотя иногда удобно, чтобы были. Они именуются вырожденными рёбрами)
С кратными рёбрами и петлями

Это означает, что в одну и ту же пару может прийти несколько рёбер
Пара означает петлю

, то есть нет различия между и
Отношение симметрично, но симметричные пары не отличимы. Аналогично, - петля.

Отображения, аналогичные тем, что даны для графов с кратными рёбрами, можно дать и для графов без кратных рёбер. В данном случае это будет означать, что отображение инъективно (каждой паре вершин соответствует ровно одно ребро, тогда как для графа с кратными рёбрами одной паре может соответствовать несколько рёбер)

Подграф
является подграфом графа , если:

  1. и
    Или так, чтобы данная диаграмма была коммутативной:
    Аналогичным образом сохраняется отличие орграфа от неорграфа.

Примеры операций над графами, создающих подграфы:

  • Исключение рёбер
  • Исключение вершин (влечёт исключение рёбер с ней, иначе нарушается коммутативность диаграммы)
  • Стягивания рёбер
    При такой операции ():
  1. Удалённое ребро мы отображаем в вырожденное ребро (С,С).
    Потому и удобно считать, что вырожденные рёбра есть. Также можно задавать граф, используя множество обычных рёбер, дизъюнктно объединённое с множеством вырожденных рёбер, то есть рёбер вида . Или, что то же самое, дизъюнктно объединить с множеством вершин ().

Определения для вершин и подграфов


Инцидентность
Пара вершина-ребро называется инцидентной, если вершина -- начало или конец ребра .

Степень вершины
Степенью (или порядком) вершины называется количество рёбер, инцидентных с вершиной.

  • Минимальная степень вершины на графе:
  • Максимальная степень вершины на графе:
    При подсчёте степени ребро-петля учитывается дважды.

Смежность

  • Вершины называются смежными, если они соединены некоторым ребром
  • Рёбра называются смежными, если они имеют общий конец
    Вершина и множество смежны, если и множество содержит вершину, смежную с . Два непересекающихся множества называются смежными, если существуют смежные вершины .

Окрестность

  • -- окрестность вершины , то есть все вершины, смежные с ней.
  • Для окрестностью называется множество всех вершин графа, смежных с . (Внутрь такой окрестности не входят вершины из самого !)

Подграф

  • Остовный подграф G -- это такой подграф, в котором множество вершин совпадает с множеством вершин G
  • Индуцированный подграф G -- это подграф, порождённый некоторым подмножеством , в котором остались рёбра, имеющие два конца на этом подмножестве

Висячая вершина
Это вершина со степенью 1

Дополнительный граф
Рассмотрим граф с тем же набором вершин, где все вершины соединены между собой (у каждой вершины степень ). Тогда дополнительным к графу на этих вершинах будет называться граф на тех же вершинах, рёбра которого есть в , но нет в .


Путь на графе

Путь на графе
Пусть
Тогда путь на графе - это последовательность невырожденных рёбер , где:

  1. Последовательность:
Для орграфа Для неорграфа
(или ) Последовательность вершин
Соответствующая ей последовательность рёбер

Путь длины ноль ведёт из вершины в неё саму
Цепь - путь, в котором рёбра не повторяются
Простая цепь, она же простой путь - путь, в котором не повторяются рёбра и вершины

"Определение"
Цикл - простая замкнутая цепь (то есть ). Разница в том, что в цепи есть выделенная вершина (цепь же идёт а -> b -> c -> a, выделенная вершина а как начало и конец цикла), а в цикле нет выделенных вершин, они там равноправны. Можно считать это отношением эквивалентности (цепь a -> b -> c -> a эквивалентна цепи b -> c -> a -> b и тд)

Теорема (без доква)
Если между вершинами есть путь, то они соединены простой цепью
Пояснение
На самом деле это достаточно простой факт. Он основан на том, что любой цикл можно просто удалить

Отношение достижимости
Путь на графе определяет отношение достижимости: это означает, что существует путь между двумя вершинами

  • w достижима из v, если есть путь из v в w
    Это отношение рефлексивно и транзитивно, а если ещё и граф является неориентированным, то тогда это отношение эквивалентности (т.е. + симметричность). Классы эквивалентности в этом случае называются компонентами связности. При этом каждая компонента такого класса эквивалентности достижимых точек -- это подграф (порождённый вершинами из одного класса эквивалентности) исходного графа
  • подграфконцы
    Важно, что элементами компоненты связности являются попарно связанные вершины. И если в неорграфе A -> B -> C -> D все четыре вершины являются отдельными компонентами связности, то в неорграфе А -- В -- С -- D это не так.

Отношение достижимости на орграфе является отношением предпорядка:
Отношение нестрогого порядка (): рефлексивное, антисимметричное, транзитивное
Отношение предпорядка: рефлексивное, транзитивное
Пусть отношение достижимости на орграфе. , если достижимо из . , если в обратную сторону тоже достижимо. Тогда -- рефлексивное, транзитивное, симметричное отношение
То есть -- отношение эквивалентности. Классы эквивалентности -- компоненты сильной связности. При этом пересечение таких компонент для неорграфа даст исходный граф, но вот для орграфа это не факт.

Матрицы, связанные с графами

Матрица инцидентности для ографа
I(G), где G -- орграф. Матрица размера VxE (столбцы -- рёбра, строчки -- вершины) в которой (v,e) равна:

  • 1, если t(e)=v (то есть ребро входит в вершину)
  • -1, если s(e)=v (то есть ребро выходит из вершины)
  • 0 иначе
    Для петли пишется 0. Петле таким образом отвечает нулевой столбец. Это не сильно удачно по причине того, что не указывается, в каком ребре есть петля.
    Это определение подходит и для графом с кратными рёбрами.

На неорграфе можно ввести ориентацию, потому что каждое ребро это технически два орребра
Для неорграфа часто считают, что компоненты берутся по модулю 2 (то есть -1 становится 1, то есть знак перестаёт влиять)

Матрица смежности
А(G) квадратная матрица VxV.

  • Для неорграфа: (v,w) равна числу рёбер, ведущих из v -> w. По диагонали -- нули. Эта матрица симметрична
  • Для орграфа: (v,w) разность между числом рёбер v -> w и числом рёбер в обратную сторону. Эта матрица кососимметрична. Обозначение []
    Ранее считали, что граф без петель. Однако если они есть, то тогда по диагонали тоже что-то пишется, причём считаем петлю дважды (для неорграфа, в орграфе по разности всё равно даст ноль). Важно, что матрица смежности для орграфа и для неорграфа разные и обозначаются по-разному.

Теорема
Для неорграфа без петель имеет следующий комбинаторный смысл:
Её компонента равна числу путей длины ведущих из
Также замечание: симметричная матрица, возведённая в степень, останется симметричной, поэтому является симметричной.
Доказательство
Индукция по q.

  • q = 0. При возведении в нулевую степень даст единичную матрицу, что является количеством искомых путей
  • q-1 -> q. Искомоечислопутей. Пример:
    \displaylines{ \begin{CD} \overset{A(G)^{q-1}} {\begin{bmatrix}
  • & - & -\
  • & - & -\
    X & X & X
    \end{bmatrix}} @.
    \overset{A(G)}
    {\begin{bmatrix}
  • & X & -\
  • & X & -\
  • & X & -
    \end{bmatrix}}
    \end{CD}
    \\
    A(G)^q_{u_3,u_2} = [\text{Кол-во путей длины q-1 от u3 до u1}]\times[\text{Кол-по путей от u1 до u2}]\+[\text{Кол-во путей длины q-1 от u3 до u2}]\times[\text{Кол-по путей от u2 до u2}]\+[\text{Кол-во путей длины q-1 от u3 до u3}]\times[\text{Кол-по путей от u3 до u2}]}
    $$

Матрица Кирхгофа
Иное название - Лапласиан графа.
Рассмотрим теперь . Это матрица размером , причём симметричная, так как умножение любой матрицы на транспонированную даст симметричную матрицу. Результат произведения не будет зависеть от ориентации графа, поэтому можно взять в том числе любой неорграф и ввести на нём произвольную ориентацию. При выполнении произведения для мы фактически скалярно умножаем две строчки: u и w. Таким образом для каждого ребра мы смотрим, вышел ли путь из одной из этих точек и вошёл ли он во вторую. Если да, произведение будет равно -1, если путь вышел из одной вершины и ушёл в другую, или вышел из другой и пришёл в какую-то из них, или путь не начинался и не заканчивался на u или w, то тогда произведение равно нулю. Колворёберсоединяющихи. (то есть ведущих u->w или w->u). По диагонали у такой матрицы стоят степени вершин: этим она отличается от -A(G).

Лемма о рукопожатиях

Лемма о рукопожатиях (для неорграфа)
Доказательство
Рассмотрим множество инцидентно. Посчитаем количество элементов в данном множестве:
Короче говоря, утверждение следует напрямую из того, что у каждого ребра ровно два конца.


Следствие
Количество вершин нечётной степени в любом графе чётно
Пояснения
Иначе бы получилось, что было бы нечётным, а оно всегда чётно по доказанной выше лемме


Деревья

Рассмотрим неориентированный граф , а также: , , Количествокомпонентсвязности.

Определения дерева и леса

  • Связный граф без циклов называется деревом.
  • Граф без циклов (связный или несвязный) называется лесом. Лес может содержать множество несвязанных деревьев. Их количество равно данного леса.
  • Мост в графе -- ребро, удаление которого увеличивает число компонент связности в графе.
  • Остовный лес -- подграф с тем же множеством вершин, а отношение эквивалентности по достижимости даёт такие же компоненты связности (где множество рёбер -- подмножество исходного множества рёбер).
  • Диаметр дерева -- максимальная длина кратчайшего пути между двумя вершинами в дереве

Ряд сведений о деревьях

  • Любое ребро в лесу или в дереве является мостом (допустим, не так; тогда удалим ребро, которое не мост, а его концы будут находиться в одной компоненте связности; однако это означает наличие цикла, который замыкался удалённым ребром; аналогично доказательство с удалением вершин в циклах). Обратное утверждение также верно (Граф, в котором каждое ребро является мостом, является лесом)
  • При стягивании вершин в лесу получается лес (допустим, не так; значит, у нас после стягивания появился цикл, но это значит, что цикл был изначально)
  • Любой граф можно довести до остовного леса, выбросив все рёбра, которые не являются мостами

Предложение

  1. равенствовыполненолес
    Доказательство
  2. Индукция по числу рёбер. С 0 рёбрами всё работает. Теперь рассмотрим удаление ребра из случайного графа. В этом случае количество рёбер уменьшится на одно, а количество компонент связности или не увеличится, или увеличится на единицу (если удалён мост). То есть есть два варианта:
    1. Такая же индукция по числу рёбер. Для леса с нуля рёбрами равенство работает. Выбрасываем из дерева в лесу ребро. Получаем на одну компоненту связности больше и на одно ребро меньше. Получим . Здесь же мы доказали, что для любого леса выполняется именно равенство
    2. Допустим, равенство выполнено не для леса. Тогда начинаем выбрасывать не-мосты. Количество компонент связности не увеличится, а вот количество рёбер уменьшится. По итогу мы получим (по предположению, что любой граф приводится к остовному лесу) лес, в котором: . Однако мы уже доказали, что в любом дереве должно выполнятся равенство. Значит, изначально был не лес, то есть равенство выполнено тогда и только тогда, когда граф -- лес.

Теорема
В дереве с вершинами ровно ребро.
Доказательство

  1. n=1. Работает
  2. Добавляем вершину к дереву. По итогу увеличим и количество вершин, и количество рёбер на 1. То есть искомое соотношение сохранится

Ранг графа

Ранг графа
Число называется рангом графа. Называется оно так по причине того, что это ранг матрицы инцидентности.
Пояснение
Матрица инцидентности строится относительно некоторой ориентации. В случае неографа ориентация может быть задана произвольно
Теорема
Доказательство

  1. Заметим, что выкидывание не-моста не меняет ранг
    Рассмотрим такую картинку:
    Очевидно, что не является мостом. Помним, что каждое ребро -- это столбец в . Получим, что: , , . В линейной комбинации они как раз и дадут : . Этот случай уже записан в общем виде. Получается, что не-мост является линейно-зависимым от столбцов других участников цикла, а значит его исключение не уменьшит количество ЛНЗ столбцов и, следовательно, не изменит ранг. Важно помнить, что ориентация может быть любая. То есть, например, ребро может выглядеть и как , и как . Поэтому мы выбираем один из знаков: выбираем некоторое направление цикла и, если направление ориентации ребра совпадает с выбранным направлением берём с минусом, иначе -- с плюсом.
  2. Благодаря пункту 1 достаточно рассмотреть данную теорему только для леса (потому что выкидывание не-мостов, то есть приведение к остовному лесу, не меняет обе части уравнения)
    Сгруппируем вершины и рёбра по их принадлежности к некоторой компоненте связности. Тогда матрица инцидентности будет иметь блочную структуру: те рёбра и вершины, что принадлежат одной компоненте, будут иметь на пересечении соответствующих строчек и столбцов значения , но те же строчки и столбцы в других местах будут иметь только значения ноль:
    перваякомпонентавтораякомпонентаперваякомпонентавтораякомпонента

При этом каждый блок является -- матрицей инцидентности компонент связности. Ранг общей матрицы становится равен сумме рангов таких вот матриц (потому что два столбца из разных блоков могут быть ЛЗ только если полностью нулевые, но они и так не посчитаются в ранг матрицы-блока, соответственно ранг общей матрицы равен количеству ЛНЗ столбцов матрицы, а значит равен количеству ЛНЗ столбцов к каждом блоке). Иным образом это можно сказать, продемонстрировав, что сумма пространства колонок каждого блока является прямой суммой.
3. [вариант док-ва от препода]. Докажем, что у любого дерева есть вершина степени 1, а если в нём есть рёбра, то их по крайней мере две. Для этого достаточно рассмотреть максимальный простой путь на данной графе. Если степень вершины не 1, то путь можно удлинить. Иначе степень равна 1. В итоге можно будет рассмотреть матрицы (при выкидывании висячей вершины связность не нарушается, используем ММИ):

\begin{CD} I(G)= {\begin{bmatrix} \pm1&0&...&0\\ 0&0&...&0&\\ ...&...&...&...&\\ \mp1&0&...&0&\\ ...&...&...&...&\\ 0&...&...&...&\\ \end{bmatrix}} \end{CD}\underset{\text{Элем. Преобр.}}{\longrightarrow} I(G)= {\begin{bmatrix} 1&0&...&0\\ 0&0&...&0&\\ ...&...&...&...&\\ 0&0&...&0&\\ ...&...&...&...&\\ 0&...&...&...&\\ \end{bmatrix}}= I(G)= {\begin{bmatrix} 1&0&...&0\\ 0&\\ ...\\ 0&&I(G\backslash\{x_0\})\\ ...\\ 0&\\ \end{bmatrix}}$$Получим: $rank(I(G\backslash\{x_0\}))=e(G\backslash\{x_0\})=e(G)-1=rank(I(G))-1 \Rightarrow rank(I(G))=e(G)=v(G)-1$ ___ (более простое док-во) 3. Благодаря предыдущему пункту достаточно проверить теорему для одного дерева. В дереве компонента связности одна, поэтому вид теоремы меняется на: $$v(G')=rank(I(G'))+1$$ Если дерево состоит из одной вершины, то это правда: ранг такой матрицы равен нулю. Если дерево невырожденное, то тогда пользуемся теоремой о том, что в дереве с n вершинами n-1 ребро и вспоминаем, что все рёбра ЛНЗ (иначе были бы циклы или несвязные одиночные вершины). Получается, теорема верна ___ ## Цикломатическое число Известно, что для любого графа $v(G)-e(G)\le c(G)$. Отсюда следует, что число $0 \le e(G)+c(G)-v(G)$ нестрого положительно (и равно ($\Leftrightarrow$) нулю в случае леса). Это число называется **цикломатическим числом графа**. **Предложение** $$\text{Цикломатичекое число равно 1}\Leftrightarrow\;\text{В графе есть ровно 1 цикл}$$ **Доказательство** 1. =\> - Получается, что раз ЦЧ не ноль, то мы имеем не лес, а значит имеем не-мостовые вершины. Получается, что если удалить такую не-мостовую вершину, мы получим лес и ЦЧ станет нулём. Другими словами, такой граф мы получаем добавлением к лесу одного не-моста. - Рассмотрим две вершины дерева (мы ведь пытаемся проложить между ними не-мост). Между ними существует ровно один простой путь, потому что иначе там был бы цикл (достаточно посмотреть на первую вершину, в которой они расходятся, и первую, в которой сходятся обратно -- это и будет цикл) - Итого: граф с ЦЧ=1 получается добавлением не-моста к дереву, а само добавление образует цикл, которых изначально в дереве не было 2. <= - Пусть в графе есть ровно один цикл. Это значит, что если удалить из него один не-мост, цикл разорвётся и получится дерево с ЦЧ = 0. Получается $e(G)+c(G)-v(G) = e(G')+1+c(G')-v(G') = 0 + 1 = 1$ - Другим числом оно не может быть в том числе и потому, что: оно не ноль, потому что не лес, потому что есть цикл; оно не больше единицы потому, что если оно не один, тогда при выкидывании ребра получаем ЦЧ не меньше единицы, что означает наличие других циклов, а их должно было быть ровно 1 Важно, что цикломатическое число объясняет только количество независимых циклов. Например, в данном неорграфе:

\begin{CD}
x_0 @= x_1 @= x_2 @=x_3\
@| @| @| @| \
x_4 @= x_5 @= x_6 @= x_7\
@.@|@|@.\
@.x_8@=x_9
\end{CD}$$
Цикломатическое число равно трём, хотя количество циклов гораздо больше

Эйлеровы графы


Эйлеров путь -- это путь, проходящий по всем рёбрам графа ровно один раз


Эйлеров цикл -- это замкнутый путь, который проходит через каждое ребро графа по одному разу.
Граф, в котором существует Эйлеров цикл, называется Эйлеровым графом


Полуэйлеров граф -- граф, в котором существует эйлеров путь


Лемма
Если в графе степень каждой вершины чётна, то начиная с любого ребра можно начать цикл, который проходит через каждое ребро единожды (но может несколько раз пройти через вершину).
Доказательство

  • Начнём обходить такой граф. Построим некоторый путь . Выбросим из изначального графа данный путь. Тогда степень вершины , если она не совпадает с , будет нечётной (в каждую вершину мы вошли столько же раз, сколько вышли, кроме ; даже если она совпадает с где-то в середине пути, в конце мы пришли в неё и не вышли). То, что в новом графе без данного пути степень нечётна означает, что она как минимум один, а значит у пути есть продолжение. Процесс, по условию , остановится тогда, когда .
    Пояснение
  1. Это ещё не эйлеров цикл. Это цикл, в котором каждое ребро содержится единожды, но это совсем не означает, что содержатся все рёбра графа. Также мы можем считать, что этот цикл простой: ведь если есть не простой цикл, то можно убрать подцикл в нём и получить простой цикл, проходящий через данное ребро:
    Здесьмызафиксировалиребро

Теорема
ГрафЭйлеровГрафсвязанивсееговершиныимеютчётнуюстепеньДоказательство

  1. => Эта часть аналогична лемме о рукопожатиях. Её результат: . (грубо говоря, мы в каждую вершину приходим столько же раз, сколько выходим из неё)
  2. <=. Связность очевидна. Смотрим на чётность степеней вершин.
    • Рассмотрим замкнутый путь, проходящий через каждое ребро единожды, максимальной длины. Допустим, мы удалим этот путь из графа (точнее, удалим рёбра данного пути). Мы получим не обязательно связный граф, но граф с чётными степенями рёбер (потому что мы вычли чётное количество рёбер для каждой вершины).
    • Пусть мы выбросили не все рёбра. Тогда есть хотя бы одно ребро, смежное с вершиной, входившей в цикл (следует из связности, раз граф связный, а выброшены не все рёбра, то можно найти путь от случайного оставшегося ребра до цикла). При этом (по лемме) в оставшемся графе каждое ребро входит в простой цикл. Получается, что мы выбросили цикл не максимальной длины, ведь можно было не "пройти мимо" того смежного ребра, а пройти сначала весь замкнутый путь до вершины, в которую входит то смежное ребро, и пройти цикл, вернувшись в ту же вершину (как бы соединив эти циклы)
    • Получим противоречие. Получается, что все рёбра в этом максимальном цикле. А значит он эйлеров

Следствие (тривиальное)
Если граф несвязный, а все вершины имеют чётную степень, то это объединение непересекающихся эйлеровых циклов


Теорема
Рассматриваем связные графы
ГрафполуэйлеровГрафимеетиливершиныснечётнойстепеньюДоказательство

  1. (=>) Если полуэйлеров путь замкнут, то этой эйлеров граф, нечётных вершин нет. Если незамкнут, то можно дополнить его одним ребром до замкнутости. Убирая обратно это ребро получим ровно две вершины с нечётной степенью
  2. (<=) Если 0, то это эйлеров цикл, а значит граф эйлеров => полуэйлеров. Если две, то соединив эти вершины получим эйлеров цикл. Убирая добавленное ребро мы размыкаем эйлеров цикл, то есть получаем эйлеров путь

Произвольно вычерчиваемый граф
Эйлеров граф называется произвольно вычерчиваемым из вершины v, если любой путь с началом в этой вершине можно продолжить до эйлерового цикла.
Пример

Произвольно вычерчиваемый из :
Не произвольно вычерчиваемый из : нельзя продолжить до ЭЦ.

Предложение
произвольновычерчиваемизЛюбойпростойциклвпроходитчерезДоказательство

  1. (=>). Допустим, не любой простой цикл проходит через . Значит, есть какой-то цикл, который не проходит через . Если выбросить этот цикл, то оставшийся граф будет эйлеровым (По лемме, так как каждая вершина четной степени). Обойдём его по этому эйлеровому циклу. Теперь вернём удалённый цикл, но обойти мы его уже никак не сможем. Значит, граф не вычерчиваемый (!!!)
  2. (<=). Рассмотрим случайный путь . Вычеркнем его из графа. У нас может получится два случая:
    • . Тогда при вычёркивании данного пути-цикла мы получим эйлеров граф (все вершины останутся чётными).
    • . Так как изначальный граф эйлеров, то существует обратный эйлеров путь
      В изначальном графе существовала лишь одна компонента связности, а после вычёркивания данного пути их количество не увеличится (иначе был бы цикл, не проходящий через ). Значит компонента связности одна, причём граф или эйлеров, или полуэйлеров => есть обратный путь, который в объединение с изначальным даст эйлеров обход
      Пояснение
  3. Граф - эйлеров
  4. См. рисунок: “Pasted image 20240801151738.png” не может быть найдена.

Двудольные графы

Граф называется двудольным, если существует разбиение , а каждое ребро имеет вид (соединяет вершину из с вершиной из ).

Ещё один вариант определения: граф называется двудольным, если у него существует правильная раскраска в два цвета: вершины можно раскрасить в два цвета так, чтобы две вершины одного цвета не были смежными.


А если можно правильно раскрасить в k цветов, то есть покрасив в k цветов не получить рядом вершины одного цвета, то этот граф называется k-дольным


Критерий двудольности графа
ГрафдвудольныйвсециклывграфеимеютчётнуюдлинуДоказательство

  1. (=>) Очевидно (потому что тогда рядом будут находиться вершины одного цвета, например, )
  2. (<=) Выдумаем такую раскраску. Достаточно это сделать для одной КС, это легко распространяется на остальные. Оказывается, что любой пусть из в имеет одинаковую чётность длины (если это не так, то простой замкнутый путь [туда + обратно] имеет нечётную длину, то есть вершина окажется одновременно окрашенной в разные цвета, а не простой можно свести к рассмотрению повторяющейся вершины, у которой сумма двух путей нечётна, а значит один из путей [до той же вершины!] нечётен).

Изоморфизм графов

Два графа и называются изоморфными, если:Такие графы фактически являются разными способами задать один и тот же граф. Его комбинаторные свойства не меняются.

Важным признаком неизоморфности графов являются отличающиеся степени его вершин. Однако вполне могут существовать графы на вершинах с одинаковыми степенями, но не изоморфные друг другу


Ещё одним способом определять изоморфность графов: теорема Уитни


Блоки, точки сочленения

Блоки и точки сочленения

Точка сочленения
называется точкой сочленения в графе , если при её удалении увеличивается число компонент связности.
Пояснение
Вершина со степенью ноль не является ТС

Предложение
точкасочленениясуществуютизоднойКСнечтолюбойпутьпроходитчерезДоказательство
Тривиально. (=>) раз кол-во увеличилось, то есть такие точки, что связаны только через
(<=) Если это не ТС, то кол-во КС не должно увеличиться. Однако после удаления больше не будет путей. То есть увеличится

Замечание
В дереве любая не висячая вершина есть точка сочленения
Доказательство
Очевидно

Замечание
Любая точка цикла не является ТС
Доказательство
Очевидно

Блок
Блок -- максимальный по включению (по количеству точек, рёбра остаются теми же, что в изначальном графе) связный подграф без точек сочленения.
Пояснение

В этом графе ТС являются , а блоком может быть подграф

Замечание
В блоке с вершинами через любые две вершины проходит простой цикл
Доказательство (смотри пояснение)

  • В данном блоке в принципе существует цикл[1]. Пусть он проходит через вершину . Докажем, что он тогда проходит и через любую другую вершину .
  • Пусть имеется цикл , содержащий , а в него не входит. Раз имеется блок, то между и циклом есть путь. Рассмотрим точку внутри цикла, сопряжённую с этим путём, и точку из пути, сопряжённую с . Временно удалим точку . Она не являлась точкой сочленения, потому есть второй путь от до . "Перерисуем" цикл: теперь он будет идти от по новому пути до , из в , из в . “Pasted image 20240731004947.png” не может быть найдена.
  • Точек, подобных , в указанном пути конечное число. Потому итеративно можно вычёркивать всё новые и новые точки до тех пор, пока не будет найден маршрут между и .
  • Имеем: в блоке есть циклы. Есть циклы между конкретной и любой другой . Зафиксируем точку : тогда существует цикл между и любой точкой . Значит, через любые две вершины проходит простой цикл
    Пояснение
  1. Иначе имеем дерево. В дереве на и более вершины есть как минимум одна не висячая. Пусть все висячие: тогда (по лемме о рукопожатиях)

Предложение
В блоке:

  1. Через любые два ребра проходит цикл
  2. Для любых двух данных вершин и одно данное ребро проходит простой путь
    Доказательство
  • Условие (1) следует из (2). Возьмём одно ребро, а второе ребро рассмотрим как две его инцидентные вершины. По утверждению (2) они соединяются простым путём. Замыкая путь вторым ребром получим цикл. Значит и рёбра соединяются циклом
  • Докажем второе утверждение. Зафиксируем ребро, проведём через него цикл[1]. Соединим вершины с этим циклом и найдём там простой путь “Pasted image 20240731005357.png” не может быть найдена.
    Следствие
  • Для любых двух случайных вершин и третьей случайной вершины существует путь, проходящий из в через . [2]
  • Для любых двух случайных вершин и третьей случайной вершины существует путь, проходящий из в , не проходящий через . [3]
    Пояснение
  1. Это возможно, потому что через любые две вершины проходит цикл, в том числе и те, которые смежны. В итоге либо ребро лежит в цикле, либо цикл можно сократить, выбросив одну из частей и поставив вместо неё ребро (левая часть рисунка)
  2. Рассмотрим вместо некоторое инцидентное с ним ребро. По условию есть путь из в через ребро, а значит и через саму .
  3. Есть путь из в через . Просто отрезаем от него вторую часть пути

Теорема

  1. Два блока имеют не более одной точки сочленения
  2. Если при этом вершина принадлежит минимум двум блокам, то () она точка сочленения
    Доказательства
  • Рассмотрим два блока с двумя общими вершинами. Объединим данные блоки. Получается, что удаление одной вершины не изменит связность графа[1]. Из этого следует, что два блока с двумя общими точками это на самом деле один и тот же блок (потому что блок - максимальный подграф).
  • (Второе утверждение, =>) Раз так, то граф распался на несвязные. Потому что иначе у них было бы больше одной общей точки. А значит, она точка сочленения[2]
  • (<=) Рассмотрим изначальную компоненту связности, содержавшую данную точку. Тогда после её удаления компонента распалась минимум на две. Рассмотрим теперь некогда существовавший путь A->Y->B. Где Y смежна с А и с В, при этом А в первой КС, а В во второй КС. Точки А и В находятся в разных блоках, потому что иначе бы имелся путь между ними, который не затрагивает Y, а тогда количество КС не увеличилось бы
    Пояснение
  1. Вообще говоря, это очевидно. То, что было первым блоком, останется связным. И вторым тоже. А соединены они через вторую точку, которую мы не удаляли.
  2. Ещё одна очевидная мысль. Рассмотрим "A->Y->B", где A лежит в первом блоке, B во втором, Y посередине и будет являться их общей точкой, причём смежной и с A, и с B. Если после удаления граф не потеряет связности, то есть ещё один путь между A->B. Тогда существует цикл, проходящий через A,Y,B и через другие точки обоих блоков. Тогда блок, состоящий их этого цикла, по наличию двух общих точек совпадает как с первым блоком, так и со вторым, что приравнивает все эти блоки друг с другом.

Висячие блоки, дерево блоков

Дерево блоков и точек сочленения

Рассмотрим граф, в котором остаются лишь блоки, которые связаны со своими точками сочленения
Pasted image 20240917100605.png Pasted image 20240917100755.png

Определение Пусть G связен. Обозначим  — блоки, а  — G. Построим двудольный граф TT, поместив  и  в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф T называют графом блоков-точек сочленения графа G.

Пояснение Почему дерево?

  1. Существует последовательность точек сочленения и блоков, соединяющая  и  и не содержащая . По ней можно проложить путь в G (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине , получив цикл. Получается, что некоторые рёбра из  и  принадлежат одному и тому же циклу, что противоречит тому, что они находятся в разных блоках.

Висячий блок
Блок называется висячим, если в нём содержится ровно одна точка сочленения исходного графа
ПояснениеВот в таком графе висячими блоками будут левый и правый.

Предложение
В связном графе:

  1. Или есть висячий блок
  2. Или нет точек сочленения
    Доказательство
  • Построим дерево блоков и точек сочленения. При отсутствии точек сочленения нет и висячих блоков. В построенном дереве, если оно не вырождено, то есть если есть точки сочленения, обязательно существуют висячие вершины. Проверим, что это могут быть только блоки
  • Это очевидно потому, что каждая ТС принадлежит минимум двум блокам. То есть имеет степень заведомо не меньше двух

Перечисление деревьев. Код Прюфера

Код Прюфера
Перед доказательством следующей теоремы рассмотрим конструкцию Кода Прюфера. Код Прюфера сопоставляет произвольному конечному дереву с n вершинами последовательность из чисел (возможно, с повторениями). Данный алгоритм сопоставляет пронумерованное дерево с последовательностью из чисел биективно

  • Для построения рассмотрим дерево. В каждый момент времени будем выбирать висячую вершину с наименьшим номером, а в последовательность будет вписывать номер связной с ней вершины. После эту висячую вершину удаляем “Pasted image 20240415020351.png” не может быть найдена.
  • Восстанавливаем исходное дерево. На первом месте стоит минимальная висячая вершина среди тех, чей номер не встречается в коде Прюфера. Рисуем её и присваиваем ей нужный номер, а также дорисовываем вершину, которая была с ней смежна. Выполняем это действие до конца кода. Осталось лишь дописать ещё одну висячую вершину к той, что была добавлена в конце “Pasted image 20240415022206.png” не может быть найдена.

Теорема (Кэли)
Число деревьев с пронумерованными вершинами равно
Доказательство

  • По сути сводится к следующей формулировке со ссылкой на код Прюфера: доказать, что существует слов длины с алфавитом из букв. Это простая задача по комбинаторике
    Пояснение
  1. Здесь имеется в виду количество деревьев с нумерацией без учёта изоморфизма. Таким образом деревья при игнорировании нумерации являются одним деревом, то есть изоморфны друг другу, но в рамках данной теоремы рассматриваются как разные

Теорема Бине-Коши (без доказательства)
Рассмотрим произведение двух прямоугольных матриц : одной размером mxn, другой -- размером nxm. В результате получится матрица mxm. Определитель такой матрицы равен:Лемма
, , , . Тогда алгебраические дополнения всех элементов данной матрицы равны
Доказательство

  • Рассмотрим взаимную матрицу. Про неё известно, что . В данном случае данное произведение равно нулю, ведь ранг не равен размерности, а значит имеются линейно зависимые столбцы/строки. Тогда любой столбец - это решение ОСЛУ формата . Откуда и получаются единицы, умноженные на константу. В итоге матрица имеет вид . Учитывая, что исходная матрица симметрична, симметрична и взаимная матрица. Потому все данные попарно равны.
    Пояснение
  1. Матрица, составленная из алгебраических дополнений. см. Алгебра
  2. Других решений нет потому, что размерность кёрнела данного отображения равна 1 по теореме о размерности ядра и образа

Матричная теорема о деревьях
Рассмотрим связный граф . Тогда все алгебраические дополнения матрицы Кирхгофа равны числу остовных деревьев данного графа
Доказательство

  • Для графа с одной вершиной доказывать нечего. Будем считать, что вершин хотя бы две
  • Рассмотрим лапласиан графа: . Получим матрицу путём вычёркивания последней строки. Легко убедиться, что определитель равен дополнению правого нижнего элемента лапласиана
  • Учитывая, что [3], используем формулу Бине-Коши:
  • Легко убедиться, что каждый такой минор равен , если матрица, составленная из с добавлением к ней вычеркнутой ранее последней строки задаёт дерево, и 0 в обратном случае[5].
    Пояснение
  1. Данное произведение просто даст тот же лапласиан, только без последней строки и последнего столбца
  2. Этого нам более чем достаточно, потому что все алгебраические дополнения равны по лемме, следовательно, нам достаточно доказать равенство количеству остовных деревьев только для одного дополнения
  3. Чтобы формула Бине-Коши не выдавала ноль автоматически нам это условие нужно
  4. Если короче, получили сумму квадратов миноров размера .

Гамильтоновы пути (Билет 14)

Гамильтонов путь
Путь, проходящий через каждую вершину по одному разу называется гамильтоновым.
Аналогично даётся определение гамильтонова цикла
Замечание

  • Аналогичное определение, но для пути, проходящего через каждому ребру по одному разу, давалось ранее - Эйлеров путь

Предложение
В полуполном орграфе существует гамильтонов путь
Доказательство

  • Индукцией по длине пути. Пусть построен некоторый путь. Рассмотрим новую, не входившую в данный путь вершину. Из неё может существовать ребро, ведущее в начало пути, или ребро, ведущее в неё из конца пути. Тогда путь легко продлевается.
  • Если пути лежат в другом направлении (то есть из первой вершины в новую и из новой вершины в последнюю), то ищем такую вершину пути, что есть путь из неё в новую, но ребро от следующей за ней вершины до новой имеет другую ориентацию
    Pasted image 20240917171807.png
    Пояснение
  1. Полуполный ориентированный граф (полуполный орграф, semi-complete digraph) - это граф, в котором любые две вершины соединены в точности одним ребром, на котором задана некоторая ориентация.
  2. Мы как бы "вставляем" новую вершину в середину пути
    Замечание
    Для того, чтобы в полуполном орграфе существовал гамильтонов цикл, достаточно, чтобы граф был сильно связан (Для любых вершин существует путь и путь ). Отметим, что из сильной связности графа следует, что в графе нет стоков и источников:
    хстоквсепутиведутВнегоисточниквсепутьидутИЗнего
    Доказательство
    image_2024-06-17_17-55-23.png
  • Если стоки и источники существуют, то очевидно, что цикла нет (потому что для цикла в вершину нужно прийти и покинуть хотя бы единожды)
  • Пойдём сначала индукцией по количеству вершин. Легко перечислить все полуполные орграфы с 3-мя вершинами и сказать, что для них условие верно. Рассмотрим теперь случайный граф. Зафиксируем некоторую вершину и обозначим её . Раз граф полуполный и ориентированный, а сама вершина не сток и не источник, то все вершины разбиваются на две категории - те, из которых есть путь до () и те, в которые есть путь из (). Причём очевидно, что существует хотя бы одна вершина, идущая из в , ведь иначе потерялась бы сильная связность. Таким образом существует цикл хотя бы длины три
  • Выделим теперь вместо одной вершины некоторый цикл . Снова разделим остальные вершины на и . Найдём дополнительные две вершины, которые легко встраиваются в уже построенный цикл. Идя так итеративно строим и весь гамильтонов цикл

Теорема Оре (Билет 15)(Достаточное условие существования гамильтонова цикла на неорграфе)
Если в графе есть несмежные вершины и для любых двух из них , то в графе существует гамильтонов цикл
Доказательство

  • Возьмём граф, удовлетворяющий данному условию, но без гамильтонова цикла, и будем добавлять в него рёбра до тех пор, пока это возможно сделать, не образовывая гамильтонова цикла [процесс называется насыщение]
  • Рассмотрим случайную пару не смежных вершин в этом насыщенном графе. Добавим между ними ребро и получим граф с гамильтоновым циклом. Понятно, что этот гамильтонов цикл проходил через это ребро. Тогда в изначальном насыщенном графе был гамильтонов путь
  • По условию Оре получается, что вершины на краях пути связаны ещё одним способом[1] (как на рисунке). Таким образом и получается гамильтонов цикл“Pasted image 20240415100437.png” не может быть найдена.
  • Таким образом мы построили "насыщенный" граф без гамильтонова цикла, в котором, однако, оказался гамильтонов цикл. Это противоречие доказывает, что изначально графов без гамильтоновых циклов с выполненным условием Оре не существует.
    Пояснение
  1. Такая картина (когда одна вершина смежна с концом пути, а следующая - с началом пути) обязательно возникнет. Пусть вершина из конца пути связана с вершинами, при этом вершина из начала пути не связана с её последующими вершинами. То есть не связана с вершинами. Получается, , откуда следует . Такой же принцип используется в более общем виде для доказательства наличия цикла длины при наличии пути длины и аналогичным условием на количество смежных вершин.
  2. Граф с гамильтоновым циклом - гамильтонов граф
    Следствие
    Теорема Дирака (Достаточное условие существования гамильтонова цикла на неорграфе)
    Если для любой вершины , то в графе существует гамильтонов цикл
    Доказательство
  • очевидно

Поиск в глубину

В теории графов используется такой объект, как корневые деревья. Одна вершина дерева объявляется корнем, после чего все рёбра ориентируются в направлении “от корня”. Один из видовых таких деревьев - DFS-деревья или деревья поиска в глубину.
Пояснение

  • Здесь и далее будем считать, что граф связен. Исходный граф именуется . Если зачем-то понадобится именовать DFS-дерево, то оно будет обозначено .

Алгоритм построения DFS-Tree
Нумеруем вершины
0. Начинаем с произвольной вершины (её номер - 1)

  1. Для данной отмеченной вершины находим неотмеченного соседа. Присваиваем ему номер и устанавливаем его как основную вершину, повторяем пункт 1
  2. Если у данной вершины неотмеченных соседей нет, возвращаемся назад
    В процессе отмечаем лишь рёбра, по которым делался переход.
    Пример
    “Pasted image 20240415122158.png” не может быть найдена.

Утверждение (тривиальное)
При обходе в глубину будут включены все вершины исходного графа

Прямые и обратные рёбра
Запустим DFS из произвольной вершины. Введем новые виды рёбер:

  • Прямые рёбра - те, по которым были переходы в DFS.
  • Обратные рёбра - то, по которым не было переходов в DFS.

Продольные и поперечные рёбра
Обратные рёбра можно разделить на две категории.

  • Продольные - если одна из его вершин является предком другой в DFT-tree
  • Поперечные - в ином случае

На показанном ниже рисунке потенциальным поперечным ребром могло бы быть ребро или . Однако для DFS-деревьев имеет место следующее утверждение:“Pasted image 20240806002350.png” не может быть найдена.
Утверждение
В дереве поиска в глубину нет поперечных рёбер
Доказательство

  • Рассмотрим некоторое ребро . Допустим, что не является потомком в DFS-дереве. В таком случае оказывается, что после прохождения их общего предка в первый раз, спуска вниз и нахождения ребра , мы поднялись до ещё раз и спустились до , которая была не отмечена.
  • Однако это входит в противоречие с алгоритмом DFS, ведь он изначально должен был пройти через все не отмеченные вершины - соседи вершины . То есть после встречи с вершина должна была быть отмечена до подъёма наверх в .
  • Следовательно, ребре просто не существует

Замечание (Это уже следующий билет - 12)
Построение DFS-дерева задаёт функцию-нумерование вершин этого дерева. Обозначим её .
Одновременно с этим можно определить функцию определённую (рекурсивно, начиная от висячих вершин) следующим образом:

  • Для висячей вершины это: [2]
  • Для не висячей это: дочерняявершина[3]
    Иначе говоря, функция - это наименьший номер вершины, в которую существует ребро из его потомка или из него самого
    Пояснение
  1. Если каждый раз при "активации" вершины - то есть при первом переходе в вершину - мы будем присваивать ей порядковый номер такой активации
  2. То есть минимальный номер смежной вершины в исходном графе
  3. То есть наименьший вершины, смежной с дочерней данной, а также наименьший номер вершины, до которой можно дойти из самой
  4. Напоминание: дочерняя вершина - это смежная вершина большей глубины
    Критерий точки сочленения
    Из сказанного выше прямо следует критерий точки сочленения:
    ТСпотомокчтоВисячий блок
    Если - висячая вершина DFS-дерева, то висячий блок будет определятся точкой предком , что:
  • У дочерней к дочки , лежащей на пути , [1]
  • Номер - наибольший из возможных [2]
    Пояснение
  1. Данное условие даёт нам гарантию, что ни из какого ещё потомка в направлении к точке не будет выходить ребро выше точки . Это же условие автоматически означает, что - точка сочленения
  2. То есть данная вершина ближе всего к самой висячей вершине , она лежит "глубже всего" в построенном дереве
  3. Данное условие в целом означает, что на пути при проходе начиная с любые два соседних ребра находятся в одном цикле, в свою очередь ребро [ - потомок по направлению к ] и ребро - любое другое ребро инцидентное - не лежат в одном цикле

Предложение (Билет 13)
ребродеревамостДлялюбойдочернейвершиныДоказательство

  • (=>) Очевидно
  • (<=) Выбросим ребро . Окажется, что то, что лежит ниже - отдельная компонента связности просто по построению
    Пояснение
  1. Всё это условие означает, что, во-первых, из ребро наверх идёт только в , а во-вторых, что ни из какого потомка вершины ребро не уходит выше .
    Следствие
  • Пусть дан связный неорграф без мостов. Тогда на нём можно ввести такую ориентацию, что получится сильно связный орграф. Для этого расставим стрелки:
    1. Вниз по прямым рёбрам
    2. Вверх по обратным рёбрам

Поиск в ширину (Билет 16)

Поиск
“Pasted image 20240420021726.png” не может быть найдена.
НА КАРТИНКЕ СЛОМАНА НУМЕРАЦИЯ, СМОТРИ НА СТРЕЛКИ!

  1. Создаётся очередь. В неё загружается вершина, с которой начинается поиск
  2. Переходим в вершину из очереди. В очередь дописываем все дочерние вершины, которые ещё не были пройдены и которые ещё не лежат в очереди. Одновременно с этим все эти дочерние вершины пишем в граф
  3. Если очередь пуста, то поиск закончен. Если нет, то перейти к пункту 2
    Очевидно, что номер родительской вершины меньше, чем номер дочерней вершины
    Ещё один важный факт: если имеются две вершины и к каждой из них своя дочерняя вершина , то .

Теорема
Введём функцию высоты. Корень дерева имеет высоту 0, каждая дочерняя вершина имеет высоту на 1 больше, чем родительская.
Тогда - длина кратчайшего расстояния от корня до в исходном графе
Доказательство

  • Если и смежные вершины, то . [тривиально]
  • Если , то . [тривиально]
  • Из этого утверждения исходное следует тривиальным образом

Раскраски

Двусвязный граф. Лемма (к теореме Брукса) (Билет 7)

k-связный граф

  • Граф называется двусвязным, если он связен и не имеет точек сочленения
  • Граф именуется k-связным, если он связен и при удалении менее вершин он остаётся связным
    Пояснение
  1. То есть двусвязный граф не теряет связности при удалении вершины

Лемма (к т.Брукса)
двусвязенминимальнаястепеньвершинывнеполныйсвязенДоказательство

  • Допустим, граф трёхсвязный. Тогда по его неполноте очевидно, что искомые вершины существуют[1]
  • Пусть граф не трёхсвязен. Тогда существует вершина , удаление которой приводит к появлению точек сочленения. Такой блок имеет висячие блоки[2]. По двусвязности исходного графа точка должна быть связана с точками и в двух разных висячих блоках.
  • При удалении вершин и из их соответствующих блоков сами блоки остаются связными. Понятно, что граф также остаётся связным.[3]
  • Из того, что степень вершины больше трёх, следует, что точка не станет изолированной в графе . Значит, этот граф связный.
    Пояснение
  1. Неполнота гарантирует существование двух несмежных вершин. Так как блок трёхсвязный, то мы можем удалить две вершины, и там появятся точки сочленения. Значит, граф имеет структуру следующего вида: имеется набор "протоблоков" - некоторых подграфов, которые после удаления двух вершин станут блоками - которые соединены, помимо точек сочленения, ещё одной точкой. Таким образом и получается искомая структура - вершины принадлежат разным блокам, а третья их связывает. В свою очередь связность графа без этих двух вершин гарантируется трёхвсязностью
  2. Было доказано ранее, что блок с точками сочленения имеет висячие блоки
  3. Удалению подлежат внутренние точки протоблоков, которые не перейдут после удаления в точки сочленения. Почему? Допустим, что станет точкой сочленения после удаления . Но тогда была точкой сочленения изначально, а значит, граф не был двусвязным
  4. См. поясняющий рисунок:“Pasted image 20240809111953.png” не может быть найдена.

Раскраска графа, хроматическое число графа. Теорема Брукса (Билет 17)

Раскраска графа

  • Правильной раскраской графа является такое отображение из в множество красок , что для всех смежных вершин и - .
  • Граф называется n-раскрашиваемым, если существует его правильная раскраска в красок

Хроматическое число графа

  • Хроматическим числом графа называется минимальное возможное число , в которое можно покрасить граф . Обозначение:

Теорема
двудольныйДоказательство

  • Очевидно следует из определения двудольного графа[1]
  • Двудо́льный граф— это граф, вершины которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной другой части. То есть, между вершинами одной и той же части рёбра отсутствуют.
    Лемма (х)
    связныйграфДоказательство
  • Проведём индукцию по количеству вершин. База - граф с - очевидна.
  • Пусть - вершина, . Рассмотрим . Все компоненты связности этого графа имели вершины, смежные с , и каждая такая вершина теперь имеет степень меньше (по 2 пункту условия). По ИП на каждой КС можно задать правильную -раскраску (а значит, и всему графу). Возвращаем , покрасив в её в один из незанятых цветов и получим искомую раскраску
    Пояснение
  1. - максимальная степень вершины
  2. Достаточно просто на каждую вершину дать свою краску
  3. , то есть смежные вершины закрашивают максимум из цветов

Теорема (Брукса)
связныйнеполныйнавершинеДоказательство

  • Пусть в данном графе степени вершин различны. В таком случае вывод напрямую следует из Леммы (х)
  • Пусть все степени вершин равны и граф имеет точку сочленения . В таком случае граф , разбивается на два графа, в каждом из которых удовлетворяется Лемма (х).[1] Очевидно, что и весь граф можно покрасить в цветов.
  • Пусть граф двусвязный. По лемме к теореме Брукса связен. Рассмотрим остовное дерево графа , корнем которого назначим вершину . Распределим вершины по уровням (то есть по расстоянию до ).
  • Начнём раскраску с вершин на самом высоком уровне (то есть с некоторых листьев дерева). На каждом уровне было покрашено максимум вершин - соседей данной вершины , исключая непокрашенного предка, который будет закрашен на следующем шаге. Значит, можно выбрать -ый цвет для .
  • Рассмотрим последний шаг раскраски. Для вершины уже покрашены все смежные вершины, которых . Выберем один цвет для , а ещё один - для (их мы красим в одинаковый цвет). Получили правильную раскраску в цветов
    Пояснение
  1. Каждый граф связен, условие 3 сохраняется, в каждом этом блоке очевидно меньше .
  2. Например, поиском в ширину

Плоские и планарные графы. Теорема Эйлера (Билет 18)

Плоский граф

  • Плоский граф - это граф, который вложен в пространство .
  • Рёбра такого графа пересекаются только в его вершинах. Запрещается пересечение рёбер не в вершинах графа
    Планарный граф
  • Планарный граф - это граф, который изоморфен некоторому плоскому графу
    Грань
  • Плоский граф разбивает плоскость, на которой нарисован, на некоторое количество граней - одну внешнюю и некоторое количество внутренних, то есть ограниченных рёбрами графа
  • Обозначение множества граней -

В рамках данного параграфа , , я буду обозначать как В, Р и Г соответственно

Теорема (формула Эйлера)
планарныйВРГДоказательство

  • Докажем индукцией по числу граней. Грань представляет из себя некоторый цикл в , который ликвидируется при рассмотрении остовного дерева. Для дерева данное соотношение очевидно (база индукции). Докидываем рёбра, образуя новые грани. Получается, что:
    • ВВ
    • РР
    • ГГ
      А значит соотношение не нарушилось

Замечание (следствие формулы Эйлера)

  • В плоском графе без висячих вершин, кратных рёбер и петель: РВ
    Доказательство
  • У каждой грани не менее трёх рёбер. Очевидно, ГР, т.е. РГ (1)
  • Получим: ВРГВРГ (2); (2) + (1) ВРРВ
    Пояснение
  • Иногда данное соотношение можно использовать для быстрого доказательства непланарности графа. Скажем, для полного графа на вершинах () получится, что .

Теорема о пяти красках (Билет 19)

Лемма (о перекрашивании вершин)

  • Если дана некоторая раскраска графа, то в графе , порождённом вершинами с цветами и , в любой компоненте связности можно поменять цвет вершин на противоположный, не нарушив правильность раскраски графа .

Теорема о пяти красках

  • У планарного графа есть правильная покраска в 5 цветов

Доказательство

  • Докажем индукцией по количеству вершин. Для всё очевидно (база индукции)
  • Пусть новая вершина. Если или количество цветов, занятых смежными вершинами, меньше , то переход очевиден
  • Пусть и заняты все 5 цветов. В таком случае рассмотрим вершины, смежные с . Рассмотрим . Если находятся в одной КС графа , то тогда - в разных КС графа . В таком случае берём КС от вершины и меняем в ней цвета и , что по лемме возможно.
    Пояснение
  • Картиночка. Напомню, что на дворе планарный граф, а значит вершина в ловушке и не может выбраться из данной КС
  • - подграф графа , порожденный всеми вершинами такими, что
    Pasted image 20240918082919.png

Покрытия

Вершинные и рёберные покрытия. Свойства чисел

Независимость вершин графа

  • Множество вершин графа называется независимым, если любые его вершины несмежны
  • Максимальный размер независимого множества над данным графом обозначается .

Паросочетания

  • Множество рёбер называется паросочетанием, если никакие два ребра не имеют общей вершины
  • Размер максимального паросочетания - .

Вершинное покрытие

  • Множество вершин покрывает граф, если любое ребро графа содержит хотя бы одну вершину из данного множества
  • Размер минимального из возможных вершинных покрытий - .

Рёберное покрытие

  • Множество рёбер покрывает граф, если каждая вершина инцидентна хотя бы одному ребру из этого множества
  • Размер минимального рёберного покрытия - .

Свойства чисел

  • [1]
  • [2]
  • [3]
  • Если нет изолированных вершин[5]: [4]
    Пояснение
  1. Рассмотрим число . Это число представляет из себя мощность множества независимых рёбер - рёбер без общих концов. Для составления минимального множества для нам потребуется взять по крайней мере по одной вершине от каждого такого ребра - иначе будет непокрытое ребро
  2. Аналогично - имеем независимые вершины в множестве мощностью . Тогда для создания рёберного покрытия нам нужно взять как минимум по одному ребру, инцидентному с каждой из этих вершин - иначе будут покрыты не все вершины.
  3. Потому что , где - максимальное множество независимых вершин, - минимальное вершинное покрытие.
  4. Докажем два неравенства:
    1. Возьмём максимальное паросочетание мощности . Это паросочетение "съело" вершин из графа, остались ещё . Значит, существует рёберное покрытие из рёбер[6], то есть (т.к. - минимальная мощность), значит, .
    2. Выберем минимальное рёберное покрытие. Оно по сути своей является подграфом на тех же вершинах. В этом подграфе, очевидно, нет циклов (иначе на одну вершину по два ребра, что противоречит минимальности). То есть это лес, причём каждая КС этого леса выглядит как звезда (опять же по минимальности нет путей длины > 2). Звезда с k+1 вершиной обычно обозначается 
      Pasted image 20240918085726.png
      Отсюда получается неравенство числоКСоднореброизкаждойКС. А значит
  5. Потому что при наличии изолированных вершин никакого рёберного покрытия в принципе не существует - изолированную вершину никаким ребром покрыть нельзя
  6. Уже взятые в (1) и по одному на каждую из (2) вершин (т.е. надо просто сложить 1 и 2), смежных между которыми нет, потому что смежность там означала бы наличие независимого ребра.

#TODO
При рассказе про паросочетания:
Лемма 4.1. Для любого графа G выполняется неравенство
χ(G) · α(G) ≥ v(G).
Доказательство. Утверждение очевидно следует из соображения о том,
что все вершины одного цвета в правильной раскраске попарно несмежны, то есть образуют независимое множество.


Теорема Бержа, теорема Кёнига, теорема Холла

Чередующийся путь

  • Пусть - паросочетание. Тогда чередующийся путь в графе по отношению к - это путь, в котором два соседних ребра отличаются относительно принадлежности к паросочетанию. То есть рёбра идут как "НП - П - НП - П - НП - ... - П - НП"

Утверждение
Если в графе есть максимальный по включению простой чередующийся путь, концы которого не принадлежат паросочетанию, то паросочетание не максимальное
Доказательство

  • Просто выбросим из "П" рёбра и добавим "НП" рёбра. Обозначим полученное паросочетание как . В нем на одно ребро больше и при том оно остается паросочетанием, так как из концов данного пути не могут идти ребра из (это следует из условия: путь был максимальным по включению) ч.т.д.

Теорема Бержа (о максимальном паросочетании в произвольном графе) (Билет 20)
немаксимальноеСуществуетмаксимальныйповключениюпростойчередующийсяпутьсконцаминеизДоказательство

  • Пусть - паросочетание с большим числом рёбер. Рассмотрим . Это подграф, степень каждой вершины которого не превосходит 2, откуда следует, что каждая его КС - это цепи и циклы.
  • Вполне очевидно, что . Также очевидно, при построении пути рёбра чередуются. Поэтому среди КС существует хотя бы один незамкнутый путь с принадлежностями вида "1 - 0 - 1 - 0 - ... - 0 - 1" - потому что иначе идёт нарушение данного выше неравенства.
  • Этот путь максимальный по включению - потому что мы рассмотрели целиком некоторую КС графа - значит, больше никаких рёбер ни от куда не выходит. Также никаких рёбер не существует и в выброшенном - потому что все рёбра их этого пересечения это рёбра , а не некотором ребре из мы закончили построения пути. Таким образом не существует "следующего" ребра из , а значит путь максимален по включению.

Теорема Кёнига (Билет 22)
ДлядвудольногографаДоказательство

  • Разделим всё множество вершин на две группы по долям двудольного графа, а после - на три класса: - вершины, которым не инцидентны рёбра из максимального паросочетания , - вершины, до которых можно дойти из по чередующимся путям и - до которых нельзяPasted image 20240918140925.png
  • Ребро между и невозможно по причине того, что это противоречит максимальности (их можно было бы записать туда)
  • Рёбра из могут соединять только и , потому что иначе можно было бы дойти чередующимся путём или . (Т.е. есть путь - противоречие). Отсюда следует, что , .
  • Рёбра из не могут соединять , потому что тогда существовал бы чередующийся путь , то есть между .
  • Рёбер между не существует по т. Бержа (потому что иначе будет макс по включению чередующийся путь )
  • , потому что известно, что на каждое ребро из нужно хотя бы одну вершину, а больше взять просто не получится. Получается, что - покрывающее множество минимального размера, а сам размер равен
    Пояснение
  1. Напомню, что совсем недавно для всех графов было доказано неравенство

Теорема Холла (Билет 23)
ВдвудольномграфеестьпаросочетаниепокрывающеевсевершиныдолиPasted image 20240918142317.png
Доказательство

  • => очевидно
  • <= докажем индукцией по количеству вершин в графе. Для графа, где , утверждение очевидно (база индукции). Далее рассмотрим два случая
    1. . В таком случае обозначим:“Pasted image 20240817175835.png” не может быть найдена. Условие теоремы очевидно выполняется для . Проверим выполнимость условия для : что противоречит условию теоремы. Значит, для условие теоремы выполнено и оба графа и , по ИП, имеют искомые вершинные покрытия, а значит и весь имеет оное
    2. . Из этого, после выбрасывания одной вершины из и другой, смежной с первой - из , автоматически следует ИП[3]. По возвращении вершин обратно вместе с их общим ребром, добавленном в паросочетание, обнаруживаем выполнение условия.
      Замечание
  • Данная теорема следует из теоремы Кёнига. Действительно, допустим, размер минимального вершинного покрытия меньше размера . Зададим это МВП. Окажется, что вершины из , не входящие в покрытие, обязаны быть связаны лишь с теми вершинами , которые вошли в покрытие (иначе получится не покрытое ребро). Но таких вершин в явно меньше. То есть мы нашли такое . Это противоречие условию приводит нас к тому, что размер МВП больше или равен размеру . Больше он, очевидно, быть не может - следовательно, он равен ему, по т. Кёнига это означает, что размер максимального рёберного покрытия равен размеру , а значит, на каждую вершину придётся по ребру из этого паросочетения
    Пояснение
  1. - первая доля двудольного графа
  2. - окрестность множества вершин - множество всех вершин, которые смежны с вершинами из этого множества, не включая сами вершины множества .
  3. Выбросим эти вершины. В таком случае , удовлетворяющее условию теоремы - значит, такой подграф подходит для ИП.

Применение т. Холла для раскраски графов

Совершенное паросочетание

  • Назовём паросочетание совершенным, если оно одновременно с этим является и рёберным покрытием

Утверждение

  • В регулярном двудольном графе существует совершенное паросочетание
  • Регулярный граф— граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей.

Доказательство

  • Пусть степени регулярного двудольного графа равны . Для любого [1] - значит, есть паросочетание, покрывающее , которое, в силу регулярности графа, равно

Следствие

  • Регулярный двудольный граф степени - объединение своих совершенных паросочетаний. Это очевидно, поскольку удаление построенного в доказательстве выше совершенного паросочетания приводит к новому регулярному графу
  • В регулярном двудольном графе степени возможна правильная рёберная -раскраска. Для её построения достаточно покрасить каждое выделенное паросочетание в свой цвет
    Пояснение
  1. Если это не так, то на меньше, чем вершин должно прийтись рёбер, то есть на каждую вершину больше, чем , что невозможно по регулярности графа

Теорема Дилуороса (Билет 25)

Частично упорядоченное множество

  • Частично упорядоченное множество - это множество с заданным отношением порядка. В нём могут существовать как элементы, состоящие в отношении, так и элементы, не состоящие в нём.[1]
  • Множество элементов, попарно не состоящих друг с другом в отношении, назовём антицепью
    Пояснение
  1. Пример такого множества: от с отношением включения. Будем иметь как , так и не состоящие в таком отношении и

Теорема (Дилуороса)

  • Частично упорядоченное множество может быть разбито на непересекающихся цепей, где - длина максимальной антицепи.
    Доказательство
  • Очевидно, что цепей не может быть меньше, чем длина антицепи - то есть
  • Рассмотрим двудольный граф, где каждая доля , а ребро существует, если относительно нашего отношения порядка.
  • Очевидно, что , где - количество непересекающихся цепей (просто потому что самое очевидное и одновременно с этим максимальное паросочетание - это паросочетание, идущее по пути прямого увеличения[1]).
  • . Данное число - это число вершин из графа на вершин, которые попали в независимое множество. В этом множестве будут как вершины, попавшие "единожды", так и вершины, попавшие "дважды"[4]. Однако очевидно, что вершин, попавших единожды, максимум . Значит вершин, попавших дважды, не менее . То есть .
    Пояснение
  1. В приведённом выше примере цепи по пути прямого увеличению могут быть: ; ; .
  2. Соотношение между
  3. т. Кёнига
  4. Здесь имеется в виду то, что исходные вершин при создании графа были дублированы и находятся как бы "друг напротив друга" на рисунке данного графа. Единожды относительно рисунка графа - значит, из двух находящихся друг на против друга вершин выбрана одна. Попадание же в пару подразумевает, что между этой парой и остальными вершинами графа нет рёбер ни в направлении из в , ни наоборот, а значит, они никак не связаны отношением порядка в .

Хроматический многочлен, хроматический индекс (Билет 26)

Хроматический многочлен

Хроматическое число графа (напоминание)

  • Хроматическим числом графа называется минимальное возможное число , в которое можно покрасить граф . Обозначение:

Хроматический многочлен

  • Количество правильных -раскрасок графа -
  • Хроматическим многочленом называется такой многочлен, что при подстановке получится

Существование хроматического многочлена

  • Если - лес из пней, то
  • Далее пойдём по индукции следующим путём: рассмотрим для графы с выброшенным ребром и со стянутым ребром[3]. Тогда
  • Утверждение далее тривиально доказывается по индукции
    Пояснение
  1. Напомню, что это - полный граф на вершинах
  2. Рассмотрим с некоторой его раскраской. Если вершины данной раскраски покрашены в разные цвета, то эту раскраску относим в . Если в одинаковый - то в .
  3. Читается как фактор .

Утверждение

  • Хроматический многочлен графа равен произведению хроматических многочленов его КС
    Доказательство
  • Очевидно из того, что компонентасвязности и из их независимости

Утверждение

  • Пусть - связный, но не -связный граф. Тогда БлокграфаДоказательство
  • Рассмотрим висячий блок в . В таком случае сначала зададим расцветку за . Из всех расцветок блока , которых , нас интересуют только те, в которых точка сочленения блока с остальным графом покрашена так же, как и в - таких способов у нас .
  • Далее доказательство идёт тривиально по индукции
    Следствие
  • Для дерева на вершинах .
  • Объединяя с предыдущим утверждением, эту формулу можно записать в виде: БлокграфаТеорема (Билет 27)
  • Кратность единицы как корня равно числу блоков
    Доказательство
  • Единица является корнем , потому что раскраска графа на более чем одной вершине с хотя бы одним ребром на 1 цвет невозможна.
  • Смотрим на общую формулу, приведённую выше. Понятно, что деление на не меняет кратность единицы как корня, если блок содержит более одной точки. В таком случае достаточно проверить, что на каждый блок кратность единицы как корня равна
  • Пусть - блок с вершинами. В существует такое ребро, что - тоже блок. Для этого достаточно стянуть любое ребро, инцидентное такой , что всё ещё блок.
  • Пусть не блок. Тогда изначально имел следующую структуру:“Pasted image 20240820181451.png” не может быть найдена.В такой структуре достаточно выбрать в качестве ребра для стягивания любое ребро .
  • Для того, чтобы доказать, что кратность как корня равна единице, достаточно доказать, что кратность как корня его производной () равна нулю
  • Далее делаем индукцию, пользуясь соотношением . Для блока на 2х вершинах это условие очевидно потому как , то есть имеет тот же знак, что . Далее считаем, что для блока с меньшим числом рёбер данное утверждение доказано. Получатся, что: имеет тот же знак, что при вершине; а граф или является блоком - тогда знак тот же, что и у , или состоит из блоков, а значит , ведь на каждый блок приходится по одной скобке .
  • Из всего вышесказанного и получается, что .

Рёберные раскраски, хроматический индекс графа (Билет 28)

Рёберная раскраска

  • Правильной рёберной -раскраской или просто рёберной -раскраской неографа называется такая раскраска рёбер, что в каждую вершину приходят рёбра разных цветов

Покрывающая раскраска

  • Покрывающая -раскраска - это такая раскраска рёбер, что в каждую вершину входят рёбра каждого из цветов

Оптимальная раскраска

  • -оптимальное раскраской называется такая раскраска, что при цветов достигается максимум суммы вида: Количествоцветоввходящихвэтувершину(то есть в остальных -раскрасках эта сумма такая же или меньше)
  • Обозначим эту сумму как . Очевидно, что Хроматический индекс
  • Минимальное , что -раскраска правильная, называется хроматическим индексом графа
  • Обозначение - . Обычно используется обозначение , но дабы не раздражать самого себя коллизией с производной хроматического многочлена да и просто ради простоты письма будет использоваться именно .
  • Очевидное утверждение:

Лемма
Доказательство

  • Очевидно. Все рёбра одного цвета составляют паросочетание не большее по размеру, чем максимальное. Получается, что минимальное случится ровно при случае .
    Следствие

Лемма об оптимальной раскраске в два цвета, теорема Кёнига о хроматическом индексе двудольного графа, теорема Гупта (Билет 29)

Лемма (об оптимальной раскраске в два цвета)

  • Рёбра связного графа можно покрасить в два цвета так, что в любой вершине будут встречаться оба цвета кроме случая, когда имеется цикл нечётной длины
    Доказательство
  • Рассмотрим вершины нечётной степени (их чётное количество по лемме о рукопожатиях) и соединим их с фантомной вершиной . Теперь все вершины имеют чётную степень, а значит в графе имеется Эйлеров цикл.
  • Начнём обход цикла, начиная с или с любой вершины степени , если такую добавлять не потребовалось. Начинаем красить, чередуя рёбра. Получается, что через каждую вершину степени мы войдём+выйдем или дважды и при этом не через или четырежды, максимум один раз через . И каждый раз входить и выходить мы будем по разным краскам
  • В начальной вершине может случиться, что начнём и закончим обход мы по одинаковым рёбрам. Но для этого мы и взяли степень больше
    Пояснение
  1. Если вдруг таких не оказалось, то мы имеем граф с вершинами степени , то есть цикл, который или очевидно красится, или имеет нечётную длину

Теорема (Кёнига, о хроматическом индексе двудольного графа)
двудольныйграфДоказательство

  • Доказываем по индукции по количеству рёбер (число исходного графа фиксируем), что у любого подграфа есть правильная раскраска в цветов. Для этого рассматриваем случайный , выбрасываем из него случайное ребро - по ИП получаем некоторый двудольный граф с как максимум . Значит, правильная раскраска существует.
  • Добавляем обратно ребро . Если среди двух вершин есть незанятый цвет, то красим ребро в него, а если такого нет, то совершаем процедуру перекрашивания двух цветов в графе так, чтобы там была правильная -раскраска (что возможно по лемме об оптимальной раскраске)[2][3]
    Пояснение
  1. Это граф, порождённый из только рёбрами с цветами и
  2. Все вершины , очевидно, степени не более двух
  3. В двудольном графе не бывает циклов нечётной длины

Теорема Гупта

  • В двудольном графе существует покрывающая раскраска в цветов
    Доказательство